Corelab Seminar
2018-2019
Eleni Bakali
On properties of counting functions with easy decision version:
completeness, approximability, Markov chains and phase transitions for TotP-complete problems
Abstract.
We consider functions that count the number of solutions to NP
decision problems. The number of solutions from NP-complete problems is
hard to compute, but there are hard counting problems with the
corresponding decision problem in P. TotP is a subclass of #P that
contains all self-reducible problems with easy decision version.
First, we will present the first completeness results for TotP,
under
parsimonious reductions, which are the strictest type of reductions.
Secondly, we present approximability results for TotP: We show how
problems can be approximated on instances with too many or very few
solutions. We find a family of instances that we prove it includes
non-approximable in polynomial-time instances (unless NP = RP). We show
that every problem in TotP admits better exponential time
approximations than the hard problems in #P. We study the relation
between TotP and FPRAS in relation to P vs RP and RP vs NP, showing on
the one hand that TotP is a subset of FPRAS if and only if NP = RP, on
the other hand FPRAS is not a subset of TotP unless RP = P.
At last, we consider weighted versions of TotP-complete problems. We
study the complexity of computing these weighted sums and show the
existence of phase transition from NP-hard to approximate to
approximable with FPRAS. We also study Markov chains for these problems
and show the existence of phase transitions from exponential to
polynomial mixing time.